1. Field of the Invention
The present invention relates generally to the routing of communications in telecommunication networks.
2. Description of the Prior Art
Telecommunication networks consist of a set of switching nodes interconnected by circuits referred to as trunk group links and define more or less complex linked structures, for instance at national scale with several hierarchical levels for the Switched Telephone Network. The prior art provides five basic routing methods : fixed, overflow, load sharing, multi-period and adaptive routing.
FIGS. 1A, 1B and 1C schematize three of these five methods for a switching node NC.sub.i of the network connected to other nodes . . . NC.sub.h, . . . NC.sub.j . . . by respective paths.
Concerning overflow routing, the principle of which is shown schematically in FIG. 1A, node NC.sub.i routes all the communications relating to a given origin and a given termination each time along the same priority path, for example in the direction of node NC.sub.j, except in the case this priority path is saturated for which the communications "overflow" onto a parallel path, for example in the direction of node NC.sub.k. All the paths are pre-established when planning the network.
Within the context of load sharing, the principle of which is schematized in FIG. 1B, node NC.sub.i does not, a priori, give preference to any path as defined in "overflow" routing. This second process therefore consists in routing a proportion .alpha. of the calls in one of the two paths, for example to node NC.sub.k, a proportion (1-.alpha.) of the calls being directed in the other of said paths, for example towards node NC.sub.j. This method requires random drawings.
The last of the methods, known as adaptive routing, shown in FIG. 1C, here schematized within the context of load sharing, consists in dynamically modifying routing parameters by using a very general principle of back-reaction regulation according to the very general automation model. In the case shown here, .alpha. varies as a function of N.sub.1, N.sub.2 and D.sub.1, D.sub.2 which designate the number of calls directed to a first path, connected to node NC.sub.j, respectively a second path connected to node NC.sub.k, and the number of calls having actually converged across this first path, and respectively the second path. Although described here within the context of load sharing, adaptive routing is used in many other applications such as approach via residual capacity.
Whatever the aforesaid methods, none of them employs income optimization criteria in the routing models which are proposed. Nevertheless, more recent control mechanisms taking into account economic factors in the working of networks appear on the scene in these latter years. Thus, to take an example, it can be referred to Bellcore's DCR-5 system which is described in the article "Implementing Dynamic Routing in the Local Telephone Companies of USA", V. P. Chaudary, K. R. Krishnan and C. D. Pack; 13th ITC conf. p. 87-91, Copenhagen, 1991. This routing system employs an adaptive method according to which indicators used for the adaptive routing of calls are managed by integrating the notion of cost (loss for the network operator). These are average costs per Erlang, modelized and computed independently of the operating of the network in real-time. Periodically, for given network configurations, several lost incomes of which the network operator is responsible are computed if respective calls are routed by each of admissible paths. These costs, or lost incomes, are computed taking account of blocking of calls subsequent to the routing of said calls. In other words, the effect of a call on the blocking of subsequent calls is simulated, these "lost" calls correspond to income losses for the network operator. Income optimization in such a system then consists in maximizing the number of calls, or more exactly, minimizing the number of blocked calls, by routing the calls on paths entailing minimum call blocking. In fact, the losses induced by the blocking of calls are expressed in terms of lost income by fixing an identical income per Erlang for each switching node in the network.
Two main drawbacks appear in the prior art as defined above:
All the routing method initially described are generally completed, in view of optimum implementation, by specific control mechanisms dealing with the minimalization of lost calls, network protection or, for example, as described above, income optimization. Specific developments are then necessary for each method and control to be carried out in the network, which do not lead to an integration unity of the different modules installed concerning the various mechanisms; consequently, functional unity and coherence cannot be achieved; and PA1 the network optimization mechanism described above within the context of the Bellcore DCR-5 system implies, due to the very fact that an income given per Erlang is allotted to each switching node, that this mechanism cannot be installed globally in the whole of the network such as the Switched Telephone Network. PA1 the economic optimization of the routing of a communication from an origin to a destination; PA1 the use of available capacities in real time in case of failures independently of the routing schemes pre-established when planning the network; PA1 differences in routing modes between networks with different switching modes (circuit, packet, . . . ), inhibiting until now any global multi-network optimization for communications using these different networks (access to a packet network via the switched network); and PA1 the modelization of the incomes in the current methods does not allow for the adaptation of different costing modes (on setting up, on the duration, on the flow), to fluctuation in traffic conditions and to users' behavior (repetition of calls, etc.). PA1 a list of routing objects is associated to the switching node, each of the routing objects including five parameters which are an upstream path parameter, an origin parameter, a destination parameter, a service parameter and a downstream path parameter, each of the five parameters being described in a tree-structural form which can be trivial for some of the parameters, and PA1 during the call procedure, a call message is transmitted, this call message including two first signalling elements defining respectively origin and destination of the communication to be set up and in the case where a tree-structure of the upstream path parameter is not trivial, a second signalling element defining an upstream path followed by the call message in the network from the origin up to the switching node. PA1 searching for routing objects of the list including origin, destination and upstream path parameters compatible with the signalling elements of the call message in that their tree-structural descriptions have depths less than those of the signalling elements, respectively, PA1 selecting among the routing objects whose origin, destination and upstream path parameters are compatible with the signalling elements, a given routing object having a maximum gain equal to a difference which is maximum, this difference being between incomes and costs accounted in real-time depending on charging information relative to various communications associated logically with the given routing object which is maximum, and PA1 associating logically the communication to be set up with the given routing object, so as to route the communication to be set up along a downstream path defined by the downstream path parameter of the routing object having the maximum gain and updating the maximum gain of the given routing object as a function of charge information of the communication to be set up after setting up of the latter, a third signalling element defining the downstream path being included in a call message to be transmitted to a switching node following the switching node along the downstream path if the downstream path defined by the downstream path parameter of the routing object having the maximum gain is described in non-trivial tree-structural form. PA1 on receipt of each of call messages or all the N call messages, N being a predetermined integer at least equal to 1, creating new routing objects in a number equal to or less than the number of parameters in a routing object, each of the new routing objects being identical to a routing object having a maximum gain with the exception of a respective parameter whose tree-structural description depth is incremented by one level, PA1 computating respective gains of the new routing objects by associating them logically with communications being set up and resulting from respective call messages whose signalling elements are compatible with origin, destination and upstream path parameters of the new routing objects, and PA1 deleting in the list each of routing objects having a segmentation gain equal to a difference, per communication, between a gain of each of said routing objects and a gain of a routing object having given rise to its creation multiplied by a number of communications associated logically to each of said routing objects, is too low as a function of a limitation in number of the size of the list. PA1 classifying routing objects into families having respective homogeneous tree-structure depths for the five parameters, and PA1 correcting gains per communication for respective routing objects of the families by deducting segmentation gains relative to a reference family into maximum corrected gains, so as the selection step consists in selecting a routing object with a corrected gain which is maximum. PA1 a) responsive to an overflow from the downstream path which is defined by the downstream path parameter of the routing object having a maximum gain to another downstream path defined by another downstream path parameter of another routing object whose origin, destination and upstream path parameter are compatible with the signalling elements and having a gain immediately lower than the maximum gain, a cost resulting from the overflow being equal to a difference between a first expected gain equal to a first gain per communication of the routing object having a maximum gain if the communication to be set up had been routed along the downstream path defined by said downstream path parameter, and a second expected gain equal to a second gain per communication along another downstream path defined by the another downstream path parameter; and PA1 b) responsive to a definitive refusal of the communication to be set up by the switching node, a cost resulting from the refusal being equal to an expected gain per communication of a last routing object whose node of a downstream path defined by a downstream path-parameter gives rise to the refusal.
These "modelized" incomes per Erlang for each of the switching nodes in the network have an economic significance and one and only one algorithm cannot manage the whole of a network with several hierarchical levels. In fact, in the case for example of the Switched Telephone Network, it is not possible to consider employing .such a method globally over the whole of said network. This would have no meaning economically: according to this method, a switching node is selected from amongst several nodes of homogeneous hierarchical level by computing the respective costs of call blocking on the trunk group links, subsequent to the routing of calls on said trunk group links. If this simulation were used for several hierarchical levels of the network, it would obviously produce incoherent results in the routing of a given call.
Apart from these two major drawbacks, certain functions remain unexploited according to the prior art: